
/*
Description:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

/**
* Definition for singly-linked list.
*/
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	/*
	I have seen lots of solutions confuse priority queue with heap. I find a good link and list the talk below.
	Concept:

	1.Heap is a kind of data structure. It is a name for a particular way of storing data that makes certain operations very efficient. We can use a tree or array to describe it.

	18
	/	\
	10	 16
	/ \   / \
	9  5  8  12

	18, 10, 16, 9, 5, 8, 12

	2.Priority queue is an abstract datatype. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation.

	A heap is a very good data structure to implement a priority queue. The operations which are made efficient by the heap data structure are the operations that the priority queue interface needs.

	*/
	//make_heap: we can access all the elements (from my answer for that solution)
	//static bool heapComp(ListNode* a, ListNode* b) {
	//	return a->val > b->val;
	//}
	//ListNode* mergeKLists(vector<ListNode*>& lists) { //make_heap
	//	ListNode head(0);
	//	ListNode *curNode = &head;
	//	vector<ListNode*> v;
	//	for (int i = 0; i<lists.size(); i++) {
	//		if (lists[i]) v.push_back(lists[i]);
	//	}
	//	make_heap(v.begin(), v.end(), heapComp); //vector -> heap data strcture

	//	while (v.size()>0) {
	//		curNode->next = v.front();
	//		pop_heap(v.begin(), v.end(), heapComp);
	//		v.pop_back();
	//		curNode = curNode->next;
	//		if (curNode->next) {
	//			v.push_back(curNode->next);
	//			push_heap(v.begin(), v.end(), heapComp);
	//		}
	//	}
	//	return head.next;
	//}

	/////////////////////////////////////////////////////////////////////////////////////
	//priority_queue: we can only get the top element (from ChiangKaiShrek's solution)
	//struct compare {
	//	bool operator()(const ListNode* l, const ListNode* r) {
	//		return l->val > r->val;
	//	}
	//};
	//ListNode *mergeKLists(vector<ListNode *> &lists) { //priority_queue
	//	priority_queue<ListNode *, vector<ListNode *>, compare> q;
	//	for (auto l : lists) {
	//		if (l)  q.push(l);
	//	}
	//	if (q.empty())  return NULL;

	//	ListNode* result = q.top();
	//	q.pop();
	//	if (result->next) q.push(result->next);
	//	ListNode* tail = result;
	//	while (!q.empty()) {
	//		tail->next = q.top();
	//		q.pop();
	//		tail = tail->next;
	//		if (tail->next) q.push(tail->next);
	//	}
	//	return result;
	//}


	/*
	struct compare {
		bool operator()(const ListNode* l, const ListNode* r) {
			return l->val > r->val;
		}
	};

	ListNode * mergeKLists(vector<ListNode *> &lists) {
		priority_queue<ListNode *, vector<ListNode *>, compare> q;
		for (auto l : lists) {
			if (l) {
				q.push(l);
			}
		}

		if (q.empty()) {
			return NULL;
		}

		ListNode* result = q.top();
		q.pop();
		if (result->next) {
			q.push(result->next);
		}

		ListNode* tail = result;
		while (!q.empty()) {
			tail->next = q.top();
			q.pop();
			tail = tail->next;
			if (tail->next) {
				q.push(tail->next);
			}
		}

		return result;
	}
	*/


	//O(NlogK) in time, O(1) in space, Divide_Conquer
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		int k = (int)lists.size();
		if (k == 0) return NULL;
		if (k == 1) return lists[0];
		return doMerge(lists, 0, (int)lists.size() - 1);
	}


	ListNode* doMerge(vector<ListNode*>& lists, int left, int right) {
		if (left == right) return lists[left];
		else if (left + 1 == right) return merge2Lists(lists[left], lists[right]);
		ListNode* l1 = doMerge(lists, left, (left + right) / 2);
		ListNode* l2 = doMerge(lists, (left + right) / 2 + 1, right);
		return merge2Lists(l1, l2);
	}


	ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
		if (l1 == l2) return l1;
		if (!l1) return l2;
		if (!l2) return l1;
		if (l1->val>l2->val) return merge2Lists(l2, l1);
		ListNode* newl2 = new ListNode(0); newl2->next = l2;
		ListNode* p1 = l1;
		while (p1->next && newl2->next) {
			if (p1->next->val<newl2->next->val) {
				p1 = p1->next;
			}
			else {
				ListNode* temp = p1->next;
				p1->next = newl2->next;
				newl2->next = newl2->next->next;
				p1->next->next = temp;
				p1 = p1->next;
			}
		}
		if (!p1->next) p1->next = newl2->next;
		delete newl2;
		return l1;
	}
	/*
	The second function is from Merge Two Sorted Lists.
	The basic idea is really simple. We can merge first two lists and then push it back. 
	Keep doing this until there is only one list left in vector. 
	Actually, we can regard this as an iterative divide-and-conquer solution.
	*/
	ListNode * mergeKLists1(vector<ListNode *> &lists) {
		if (lists.empty()) {
			return nullptr;
		}
		while (lists.size() > 1) {
			lists.push_back(mergeTwoLists(lists[0], lists[1]));
			lists.erase(lists.begin());
			lists.erase(lists.begin());
		}
		return lists.front();
	}
	ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
		if (l1 == nullptr) {
			return l2;
		}
		if (l2 == nullptr) {
			return l1;
		}
		if (l1->val <= l2->val) {
			l1->next = mergeTwoLists(l1->next, l2);
			return l1;
		}
		else {
			l2->next = mergeTwoLists(l1, l2->next);
			return l2;
		}
	}

	ListNode * mergeKLists0(vector<ListNode*>& lists) {
		ListNode * phead = new ListNode(0);
		ListNode * p = phead;
		ListNode * t;
		if (lists.size() == 0)
		{
			return nullptr;
		}
		else if (lists.size() == 1)
		{
			return lists[0];
		}

		//phead->next = lists[0];

		for (auto l : lists)
		{			
			while (l != nullptr)
			{
				t = l->next;

				p = phead;
				while (p->next != nullptr)
				{
					if (p->next->val >= l->val)
					{						
						l->next = p->next;
						p->next = l;
						break;
					}
					
					p = p->next;
				}	

				if (p->next == nullptr)
				{
					l->next = nullptr;
					p->next = l;
				}

				l = t;
			}
		}

		return phead->next;
	}
};

int _mergeKLists()
{	
	vector<vector<int>> nums{ {1, 4, 5}, { 1,3,4 }, { 2,6 } };
	
	Solution solu;
	vector<ListNode*> lists;
	ListNode *phead;
	ListNode *p;
	ListNode *mlist;

	for (auto v : nums)
	{
		phead = new ListNode(0);
		p = phead;
		for (auto n : v)
		{			
			p->next = new ListNode(n);
			p = p->next;
		}
		lists.push_back(phead->next);
	}	
	cout << "lists: " << endl;
	for (auto l : lists)
	{
		while (l != nullptr)
		{
			cout << l->val << " ";
			l = l->next;
		}
		cout << endl;
	}

	mlist = solu.mergeKLists(lists);

	cout << "merged list: " << endl;
	while (mlist != nullptr)
	{
		cout << mlist->val << " ";
		mlist = mlist->next;
	}
	cout << endl;

	return 0;
}